package com.wenhao.leetcode.medium;

import com.wenhao.leetcode.structure.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 题目：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 * 从中序与后序遍历序列构造二叉树
 * @author Wenhao Tong
 * @create 2021-07-11 11:04
 */
public class LeetCode106 {
    public static void main(String[] args) {

    }
    Map<Integer,Integer> inorderIndex = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0;i < inorder.length;i++) {
            inorderIndex.put(inorder[i],i);
        }
        return getSubTree(postorder,0,0,postorder.length);
    }
    private  TreeNode getSubTree(int[] postorder,int postHi,int inHi,int size) {
        if (size == 0) {
            return null;
        }
        TreeNode treeNode = new TreeNode(postorder[postHi]);
        int index = inorderIndex.get(postorder[postHi]);
        int size1 = inHi - index;
        TreeNode rightChild = getSubTree(postorder, postHi - 1, inHi, size1);
        TreeNode leftChild = getSubTree(postorder,postHi - 1 - size1,inHi - size1 - 1,size - size1 - 1);
        treeNode.left = leftChild;
        treeNode.right = rightChild;
        return treeNode;
    }
}
